/*
 * @Author: szx
 * @Date: 2022-03-01 15:05:44
 * @LastEditTime: 2022-03-01 15:15:37
 * @Description: 
 * @FilePath: \leetcode\300-399\347\347_2.cpp
 */
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
   public:
    //小顶堆
    class mycomparison {
       public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for (int i : nums) {
            map[i]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值
        for (auto it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
            if (pri_que.size() > k) {
                pri_que.pop();
            }
        }
        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};